# PROBLEM STATEMENT:
# ==================
# Given an array X, find the j and i that maximizes Xj - Xi, subject to the
# condition that i = j. If two different i,j pairs have equal differences,
# choose the "leftmost shortest" pair with the smallest i and, in case of a tie,
# the smallest j. 
# 
# For instance, given an array [4, 3, 9, 1, 8, 2, 6, 7, 5], the maximum
# difference is 7 when i=3 and j=4. Given the array [4, 2, 9, 1, 8, 3, 6, 7, 5],
# the maximum difference of 7 appears at two points, but by the
# leftmost-shortest rule the desired result is i=1 and j=2. I and j need not be
# adjacent, as in the array [4, 3, 9, 1, 2, 6, 7, 8, 5], where the maximum
# difference of 7 is achieved when i=3 and j=7. If the array is monotonically
# decreasing the maximum difference is 0, which by the leftmost-shortest rule
# occurs when i=0 and j=0.
#
# SOLUTIONS:
# ==========
# There are two solutions provided here. One is a naive solution that used two
# nested loops comparing diff of all possibilities while walking index i,j. This
# one runs in O(n^2).
# 
# The other solution provides better linear time complexity (O(n)). It works by
# keep extending j and update it if it finds a better maximum. At the same time
# it keeps track of the lowest minumum value seen so far (not index i) and see
# if the current value against the lowest minimum makes better maximum. If so
# then we found new i and j indices.

import random

def naive_solution(input):
   length = len(input)
   i, j = 0, 0
   current_max = input[j] - input[i]
   for ii in range(0, length):
      for jj in range(ii, length):
         if input[jj] - input[ii] > current_max:
            i, j = ii, jj
            current_max = input[j] - input[i]
   return i, j, current_max

def linear_solution(input):
   length = len(input)
   i, j, m = 0, 0, 0
   current_max = 0
   for k in range(1, length):
      if input[k] - input[i] > current_max:
         j, current_max = k, input[k] - input[i]
      if input[k] - input[m] > current_max:
         i, j = m, k
         current_max = input[k] - input[m]
      if input[k] < input[m]: m = k
   return i, j, current_max

# main code of the program. We run several loops and verify that the results,
# however the list is shuffled, still match between naive and linear solutions
if __name__ == "__main__":
   INPUT = list(range(20))
   for i in range(20):
      random.shuffle(INPUT)
      a1, a2 = naive_solution(INPUT), linear_solution(INPUT)
      print("Input:", INPUT)
      print("Naive solution: i = %d, j = %d, diff = %d" % a1)
      print("Linear solution: i = %d, j = %d, diff = %d" % a2)
      print()
      assert a1 == a2


